A searchable encryption scheme—SSE—enables a party to encrypt a message, index the obtained ciphertext, and at any point in time to efficiently look for the plaintext by issuing a search token encoding a search criterion. In addition, an SSE scheme is called dynamic, if documents or search tags are arbitrarily inserted or deleted from the system. SSE can be used in settings where a party would like to outsource some data while it still wishes to maintain some privacy guarantees. The number of applications that dynamic SSE have is vast. They range from databases with the desiderata of supporting a rich set of operations over a large amount of data, e.g. CryptDB to file systems where tons of users push, pull and delete files, but data is accumulated for a finite period of time.